package com.backpack;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * 回文子串
 * 输入：s = "abc"
 * 输出：3
 * 解释：三个回文子串: "a", "b", "c"
 */
public class PalindromicSubstrings0120_647 {
    public int countSubstrings(String s) {
        //动态规划思路
        //dp[][] 含义：表示以下标[i,j]范围的子字符串 是否是回文子串
        //返回值 res
        int res = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];

        //初始化：都是 false

        //遍历顺序：因为 dp[i][j] 依赖于 dp[i+1][j-1], 所以二维数组应该 从下往上、从左往右遍历。
        for (int i = s.length()-1; i >=0 ; i--) {
            for (int j = 0; j <= s.length() - 1; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if(j-i<=1) {dp[i][j] = true; res++;}
                    else if (dp[i+1][j-1]){
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
        }
        return res;

    }
}
